//https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking

#include <stdio.h>
#include<stdlib.h>

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val;

};

struct TreeNode* PreCreat(char* a, int* i)
{
    //遇到'#'就返回NULL
    if (a[*i] == '#')
    {
        (*i)++;
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (root == NULL)
    {
        perror("malloc fail\n");
        return NULL;
    }
    root->val = a[(*i)++];
    root->left = PreCreat(a, i);
    root->right = PreCreat(a, i);

    return root;

}

void InOrder(struct TreeNode* root)
{
    if (root == NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ", root->val);
    InOrder(root->right);


}

int main() {
    char a[100];
    scanf("%s", a);

    int i = 0;
    struct TreeNode* root = PreCreat(a, &i);
    InOrder(root);

    return 0;
}